package com.jxb.first;

import java.util.Collections;
import java.util.LinkedList;
import java.util.Stack;

/**
 * 字符串解码
 */
public class DecodeString_394_UseStack1 {

    public static void main(String[] args) {
        String s = "a4[b]2[bc]d";
        String s1 = decodeStringLinkList(s);
        System.out.println(s1);
    }

    static int idx = 0;

    //栈
    //设置2个栈：一个存放[字符前的解码结果；一个存放数字
    //逻辑：
    //  1：先去判断是否是数字，若是数字，获取完整的数据，压倒数字栈
    //  2：再去判断是否是字符，若是字符，拼接字符
    //  3：判断是否是[字符，若是，将前面的结果字符压入到结果栈，再将暂存字符的变量置为null
    //  4：判断是否是]字符，若是，将字符栈进行出栈获取前面的结果字符；然后将数字栈进行出栈，获取数字，通过数字进行循环遍历通过暂存字符变量拼接结果字符
    public static String decodeStringStack(String s) {
        String res = "";
        Stack<Integer> stackInt = new Stack<>();
        Stack<String> strStack = new Stack<>();
        while (idx < s.length()) {
            char c = s.charAt(idx);
            if (Character.isDigit(c)) {
                //获取完整的数字
                int totalNumber = getDigit(s);
                stackInt.push(totalNumber);
            }
            else if (c == '[') {
                //将[之前的数据放入栈中
                strStack.push(res);
                res = "";
                idx++;
            }
            else if (c == ']') {
                //获取栈中之前的数据
                StringBuilder lastRes = new StringBuilder(strStack.pop());
                //获取数字
                Integer pop = stackInt.pop();
                for (int i = 0; i<pop; i++) {
                    lastRes.append(res);
                }
                res = lastRes.toString();
                idx++;
            }else {
                res = res + c;
                idx++;
            }
        }
        return res;
    }

    //链表
    //1：将数字、普通字符和‘]’全部入栈
    //2：当当前字符是']'，取出'['后的所有字符，进行反转拼接，然后移除'['字符，获取数字，根据数字进行循环拼接，添加到结果链表中
    //3：循环结束，将结果链表转成字符串，返回
    public static String decodeStringLinkList(String s) {
        LinkedList<String> resList = new LinkedList<>();
        while (idx < s.length()) {
            char c = s.charAt(idx);
            //判断是否是数字
            if (Character.isDigit(c)) {
                int digit = getDigit(s);
                resList.addLast(String.valueOf(digit));
            }
            //处理普通字符和”]“
            else if (c == '[' || Character.isLetter(c)) {
                resList.addLast(String.valueOf(c));
                idx++;
            }
            //判断是否是]字符
            else if (c == ']') {
                LinkedList<String> list = new LinkedList<>();
                while (!"[".equals(resList.peekLast())) {
                    list.addLast(resList.removeLast());
                }
                //反转字符
                Collections.reverse(list);
                //取出‘]’字符
                resList.removeLast();
                //获取数字
                int count = Integer.parseInt(resList.removeLast());
                //构造字符串，进行拼接
                StringBuilder sb = new StringBuilder();
                for (String s1 : list) {
                    sb.append(s1);
                }
                StringBuilder resSb = new StringBuilder();
                for (int i = 0;i<count;i++) {
                    resSb.append(sb);
                }
                resList.addLast(resSb.toString());
                idx++;
            }
        }

        //获取字符
        StringBuilder sb = new StringBuilder();
        for (String rs : resList) {
            sb.append(rs);
        }
        return sb.toString();
    }

    private static int getDigit(String s) {
        StringBuffer ret = new StringBuffer();
        while (Character.isDigit(s.charAt(idx))) {
            ret.append(s.charAt(idx++));
        }
        return Integer.valueOf(ret.toString());
    }



}
